# -*- coding: utf-8 -*-
# @Time    : 2019/3/5 18:59
# @Author  : z.t.b
# @Email   : zhtbin@163.com
# @File    : mergeSort.py
# @Software: PyCharm
"""
归并排序
数组A从中间分成两部分B,C，分别排序
然后合并（从B,C中取一个比较，将小的或大的放入结果数组D，知道BC为空）
"""
import sys


class Solution(object):

    def sort(self, arr):
        if not arr or len(arr) <= 1:
            return arr
        arr_len = len(arr)
        mid = arr_len // 2
        arr1 = arr[0:mid]
        arr2 = arr[mid:]
        return self.merge(self.sort(arr1), self.sort(arr2))

    def merge(self, arr1, arr2):
        result = []
        if not arr1:
            arr1 = []
        if not arr2:
            arr2 = []
        while len(arr1) > 0 or len(arr2) > 0:
            if len(arr1) > 0:
                num1 = arr1[0]
            else:
                num1 = sys.maxsize
            if len(arr2) > 0:
                num2 = arr2[0]
            else:
                num2 = sys.maxsize
            if num1 <= num2:
                result.append(num1)
                del arr1[0]
            elif num2 < num1:
                result.append(num2)
                del arr2[0]
        return result


if "__main__" == __name__:
    solution = Solution()
    print(solution.sort([110, 666, 222, 9, 10, 3, 100, 20, 5, 88, 8]))
